Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 1 на тему: " Програмування машин Тьюрінга " з дисципліни: " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ " № варіанта = [21+ 77] % 30 + 1=9  1. МЕТА РОБОТИ Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга. ПОСТАНОВКА ЗАДАЧІ 2.1. Загальна частина Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Використання додаткових символів, що не входять в алфавит А, має бути обгрунтоване. Скласти програму для мишини Тьюрінга. В початковому стані каретка МТ має розпізнавати перший зліва символ вхідного слова Р. В кінцевому стані каретка МТ має зупинитись під одним із символів вихідного слова (під яким саме - не має значення). Відлагодження і тестування програми провести в середовищі емулятора мишини Тьюрінга. Записати в середовищі емулятора в поле Условие задачи варіант і умову індивідуального завдання. В поле Комментарий записати коротке пояснення дій, які реалізуються у відповідних станах каретки. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МТ. 2.2. Індивідуальне завдання 9. A={a,b,c}. Замінити в непорожньому слові P кожне входження символів bc на символ a. СЛОВЕСНИЙ ОПИС АЛГОРИТМУ Для розв'язання цієї задачі потрібно виконати наступні дії: Вихідне слово будемо будувати справа від вхідного. Щоб розмежувати ці слова, відокремимо їх деяким допоміжним символом, відмінним від всіх символів алфавіту A, наприклад знаком = (крок 1). Після цього повертаємось до початку вхідного слова (крок 2).
Далі в циклі копіюємо і переносимо всі символи вхідного слова, крім символа c, вправо за знак =, тобто формуємо вихідне слово. Для цього аналізуємо кожний символ вхідного слова і заміняємо його на двійника. Якщо це символ c, то повертаємося до попереднього символа (крок 4). Якщо попередній символ b, то біжимо вправо до першої вільної комірки (крок 5). Повертаємося на 1 символ вліво (останній символ вихідного слова) і заміняємо його на символ a (крок 6). Якщо ж цей символ відмінний від b, то записуємо символ c вкінці вихідного слова.
Коли буде скопійовано останній символ вхідного слова і повернуто до його двійника, то потім після переміщення на одну позицію вправо потрапимо на знак = (крок 6). Це сигнал про те, що вхідне слово повністю скопійовано, тому роботу МТ треба завершувати, а кретку перемістити на 1 символ вліво.
3.1. Обгрунтування вибору додаткових символів, що не входять в алфавит А Щоб розмежувати вхідне і вихідне слово, я відокремив їх деяким допоміжним символом, відмінним від всіх символів алфавіту A, знаком =. Оскільки я копіюю вхідне слово, то записавши справа копію чергового символу, потрібно повернутися до вхідного слова в позицію цього символа, і потім переміститися вправо до наступного символа, щоб скопіювати вже його. Щоб довідатися в яку позицію вхідного слова треба повернутися, вводимо додаткові символи. Коли ми опиняємось в цій позиції в перший раз, то заміняємо символ, що в ній знаходиться, на його двійника - на новий допоміжний символ, причому різні символи заміняємо на різні двійники : a на A , b на B , с на С. Після цього виконуються якісь дії в інших місцях стрічки. Щоб потім повернутись до потрібної позиції, треба просто відшукати на стрічці ту комірку, де перебуває символ A або B. Саме для відновлення колишнього символу і треба було ввести додаткові символи. АЛГОРИТМ У ВИГЛЯДІ ПРОГРАМИ ДЛЯ МТ Повна таблиця   a0 a b c = A B C Пояснення  q1 q2=L q1aR q1bR q1cR         ставимо знак = після слова  q2 q3a0R q2aL q2bL q2cL         йдемо вліво на 1-й символ  q3   q4AR q8BL q6CR q0=L       аналіз і заміна чергового символа  q4 q7a q4aR q4bR q4cR q4=R       запис а зправа  q5 q7b q5aR q5bR q5cR q5=R       запис b зправа  q6 q7c q6aR q6bR...